//
// Created by daiyizheng on 2022/4/12.
//
#include <vector>
using namespace std;
#include <algorithm>
//最简单的方式：保留求和
int maxSubArray(vector<int>& nums) {
    int Maxsum = INT_MIN;
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = i; j < nums.size(); ++j) {
            int sum = 0;
            for (int k = i; k <= j; ++k) {
                sum+=nums[k];
            }
            Maxsum = max(sum, Maxsum);
        }
    }
    return Maxsum;
}

//动态规划 区间问题 从i->j的最大值 d[i][j]表示区间[i, j]的累加和
//初始化 对角线 dp[i][i] = nums[i]
//初始化 i=0 dp[0][j] = dp[0][j-1] + nums[j]
//状态转移 dp[i][j] = dp[i-1][j] - dp[i-1][i-1] 或者 dp[i][j] = dp[i-1][j] - nums[i-1]
int maxSubArray1(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    //初始化
    dp[0][0] = nums[0];
    int maxSum = dp[0][0];
    for (int i = 1; i < nums.size() ; ++i) {
        dp[0][i] = dp[0][i-1]+nums[i];
        maxSum = max(maxSum, dp[0][i]);
    }

    //状态转移
    for (int i = 1; i < nums.size(); ++i) {
        for (int j = i; j < nums.size(); ++j) {
            dp[i][j] = dp[i-1][j] - dp[i-1][i-1];
            maxSum = max(maxSum, dp[i][j]);
        }
    }
    return maxSum;
}

//动态规划优化
int maxSubArray2(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 0);
    //初始化
    dp[0] = nums[0];
    int maxSum = dp[0];
    for (int i = 1; i < nums.size() ; ++i) {
        dp[i] = dp[i-1]+nums[i];
        maxSum = max(maxSum, dp[i]);
    }

    //状态转移
    for (int i = 1; i < nums.size(); ++i) {
        for (int j = i; j < nums.size(); ++j) {
            dp[j] = dp[j] - dp[i-1];
            maxSum = max(maxSum, dp[j]);
        }
    }
    return maxSum;

}

// 动态规划(改变状态定义)
// 时间复杂度：O(n)
// 空间复杂度：O(n)
int maxSubArray3(vector<int>& nums) {
    // 状态定义：dp[i] 表示以索引为 i 的元素结尾的最大子数组和
    vector<int> dp(nums.size());

    // 状态初始化
    dp[0] = nums[0];
    int maxSum = dp[0];

    // 状态转移
    for (int i = 1; i < nums.size(); i++) {
        dp[i] = max(dp[i - 1] + nums[i], nums[i]);
        maxSum = max(maxSum, dp[i]);
    }

    return maxSum;
}

// 动态规划(改变状态定义) + 状态压缩
// 时间复杂度：O(n)
// 空间复杂度：O(1)
int maxSubArray4(vector<int>& nums) {
    // 状态初始化
    int preMaxSum = nums[0];
    int maxSum = preMaxSum;

    // 状态转移
    for (int i = 1; i < nums.size(); i++) {
        preMaxSum = max(preMaxSum + nums[i], nums[i]);
        maxSum = max(maxSum, preMaxSum);
    }

    return maxSum;
}